package com.zy.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhaoyi
 * @date 2021/12/21 5:34 下午
 * 广度优先
 */
public class DFS {

    static boolean found = false; //全局变量或者类成员变量

    public static boolean search(Graph graph, Integer src, Integer dest) {
        found = false;
        boolean[] visited = new boolean[graph.getCount()];
        int[] prev = new int[graph.getCount()];
        for (int i = 0; i < graph.getCount(); i++) {
            prev[i] = -1;
        }
        recurDfs(graph,src, dest, visited, prev);
        BFS.print(prev, src, dest);
        return found;
    }

    private static void recurDfs(Graph graph,Integer src, Integer dest, boolean[] visited, int[] prev) {
        visited[src] = true;
        if (src.equals(dest)) {
            found = true;
            return;
        }
        LinkedList<Integer>[] table = graph.getTable();
        for (Integer integer : table[src]) {
            if (!visited[integer]){
                prev[integer] = src;
                recurDfs(graph,integer,dest,visited,prev);
            }
        }
    }

}
